from typing import List


class Node:
    def __init__(self, val=None, children=None):
        if children is None:
            children = []
        self.val = val
        self.children = children


def levelOrder(root: Node) -> List[List[int]]:
    # 递归实现 记录每个节点的层数
    def traverse_node(node, level):
        if len(result) == level:
            result.append([])
        result[level].append(node.val)
        for child in node.children:
            traverse_node(child, level + 1)

    result = []

    if root is not None:
        traverse_node(root, 0)
    return result


if __name__ == '__main__':
    n1 = Node(1)
    n2 = Node(3)
    n3 = Node(2)
    n4 = Node(4)
    n5 = Node(5)
    n6 = Node(6)
    n1.children = [n2, n3, n4]
    n2.children = [n5, n6]
    print(levelOrder(n1))
